2022 알고리즘 기말고사

(1) 시험시간 : 6월 15일(수요일) 오전 8시 30분 - 10시 20분

(2) 풀이 중간과정을 충분히 기술하여 채점자에게 도움이 되도록 하세요.

풀이 과정이 충분하지 않거나 최종 답만 적으면 감점됩니다.

(3) 뒷면에 답을 쓰게 되면 작성자가 이 사실을 문제에 표시하기 바랍니다.

학번	이름	감독자 확인

문제 (배점)	점수	문제 (배점)	점수
1 (30)		4 (40)
2 (40)		5 (40)
3 (30)		6 (50)
		총합계 (230)

[1] 1차원 배열 X[N]에 숫자가 정렬된 순서로 저장되어 있다. 우리는 어떤 숫자 [eqn: k]가 이 배열에 있는지를 ternary search(3분 탐색)로 검사하려고 한다. ternary search는 전체 탐색할 공간을 3개의 거의 같은 크기인 [eqn: n/3]으로 분할하여 각 경계의 자료가 [eqn: k]인지를 검사한다. 만일 아니라면 다시 답이 존재할 구간을 찾아서 탐색을 진행한다. 이 ternary search 알고리즘의 최악 시간 복잡도 [eqn: T(N)]를 [eqn: Theta(``)] 기준으로 계산하시오.

(채점 기준)

◾ 아래와 유사한 과정을 통해 [eqn: 1+2log _{3} n]를 도출했으면 30점.

[eqn: T(n) & =T( {n} over {3} )+2# & =T( {n} over {3 ^{2}} )+2 CDOT 2# & =T( {n} over {3 ^{3}} )+3 CDOT 2# & = CDOTS # & =T( {n} over {3 ^{k}} )+k CDOT 2] …□

[eqn: k=log _{3} n]으로 두면, …□

[eqn: T(n) & =T( {n} over {3 ^{log _{3} n}} )+(log _{3} n) CDOT 2# & =T(1)+2log _{3} n# & =1+2log _{3} n]

◾ 위의 계산과정과 다른 형태의 풀이일 경우 아래의 기준을 적용함.

1. 전개 과정에서 실수한 경우(답의 유사도에 따라 2번의 부분점수 추가 적용.)

□-1. 처음 식의 정의를 잘못 내렸다면 5점.

□-2. 전개 과정에서 실수한 경우 10점.

□-1. 마지막 계산과정에서 실수했다면 15점.

2. 답만 있는 경우(유사도에 따라 ±1~2점의 차이가 있을 수 있음.)

[eqn: log _{2} n] - 5점, [eqn: log _{3} n] - 10점, [eqn: 2log _{3} n]- 15점.

[2] 두 개의 배열 X[ ], Y[ ]이 있을 때, 정렬이 된 X[ ], 정렬되지 않은  Y[ ] 이 있다. 우리는 이 두 배열에서 같은 원소가 몇 개나 존재하는지를 확인하고자 한다. 각 배열의 크기는 [eqn: vert X``vert]= [eqn: n], [eqn: vert Y``` vert]= [eqn: m] 이라고 가정한다. 아래의 다양한 경우에 이 공통원소의 갯수를 계산하는 효율적인 알고리즘을 제시하고, 제시한 알고리즘의 복잡도를 [eqn: n,`m]의 함수로 표시하시오. 이때, [eqn: n]과 [eqn: m]의 차이에 따라 다른 알고리즘을 고려해야 한다. (각10점)

a) sorted [eqn: vert X`` vert]= [eqn: n], [eqn: vert Y``` vert]= [eqn: k] ([eqn: k]는 5보다 작은 상수. 즉 [eqn: k`<`5])

- Y의 원소를 X에서 이진 탐색을 한다. 시간은 [eqn: THETA (`k``log _{2} `N``)]

b) sorted [eqn: vert X`` vert]= [eqn: n], [eqn: vert Y`` vert]= [eqn: m] ≈ [eqn: n] (X와 Y의 크기는 거의 같다.)

- Y를 정렬한 다음 두 X,Y를 head merge(정렬된 두 배열의 원소를 앞에서부터
서로 비교해나가는 병합 merge 알고리즘), 따라서 [eqn: m`log`m] + [eqn: n+m], m과 n이 거의 같으므로 결국 이것의 order는 [eqn: O(n`logn)]도 되지만 문제에서 [eqn: n,m]으로 표시하라고 요구했기 때문에 [eqn: O(n`logn)] 이렇게만 쓴 경우 약간의 감점.

c) sorted [eqn: vert X`` vert]= [eqn: n], [eqn: vert Y`` vert]= [eqn: m] = [eqn: sqrt {`n`}]

- 만일 (a)와 같이 할 경우, Y의 각 원소를 X에서 binary search를 수행하면 그 시간은  [eqn: w(m,n)`=`m``log`n]이다. 만일 (b)와 처리할 경우 [eqn: m`log``m= sqrt {n} log`` sqrt {n}] 시간에 Y를 정리한 다음 head merge를 하면 그 정확한 시간은

[eqn: m`log`m`+`n`+`m`=` sqrt {n} ``log``n ^{1/2} +n+m= {sqrt {n}} over {2} ``log``n+n+m]

order로 표시하면 [eqn: O(n+m)]이 되지만 위와 같은 식이 정답. 계산과정 없이 그 결과를 [eqn: O(n+m)]이렇게만 표현한 경우 약간의 감점. Y의 [eqn: sqrt {n}]개의 원소를 X에 그대로 binary search를 해도 같은 복잡도.

d) sorted [eqn: vert X`` vert]= [eqn: n], [eqn: vert Y`` vert]= [eqn: m] = [eqn: log_2`` {`n`}] =>(c)와 같은 방법으로 풀이

- [eqn: O(m``log``n)=O(``log ^{2} ``n)]으로 표시한 경우 모두 정답으로 표시. 만일 Y를 정렬하는 경우라면 그 시간은 [eqn: log _{2} ``n`log _{2} (log _{2} n)+log _{2} n+n]이 되는데, 이것의 전체 차수는 결국 O(n)이 되므로 Y를 X에 binary search를 할 때 걸리는 시간 [eqn: O(m``log``n)=O(``log ^{2} ``n)] 보다 높아서 안 됨.

요약: Y가 적절히 큰 경우에는 Y를 정렬하여 X와 head merge를 해야 하고, Y의 크기가 작은 경우에는 Y의 각 원소를 X를 대상으로 바로 binary search 하는 것이 더 나은 시간 복잡도가 보장됨.

[3]  5개의 원소를 가진 집합 S = [eqn: LEFT { ~4,~9,~12,~15,~29`` RIGHT }] 이 있을 때, 집합 S에서 그 총합이 K가 되는 부분집합 R이 존재하는지를 알아보려고 한다. 즉 sum of subset 문제를 backtracking으로 해결하려고 한다.

만일 K=24일 때 backtracking tree를 통하여 푸는 과정을 보이시오. 단 고려하는 숫자는 크기 순서는 오름차순, 즉 4, 9, 12, 15, 29로 한다. 그리고 더 이상 답이 존재하지 않을 때는 pruning을 해야 하고, 이 상황을 tree에 표시해야 한다.

(채점 기준)

◾ 아래의 조건을 만족하면 30점.

1) 정답 집합 {9,15}를 찾았고, pruning이 정확하게 수행되어

backtracking tree가 제대로 구성된 경우.

2) 정답 집합 {9,15}를 찾았고, pruning이 정확하게 수행되었으며,

찾은 시점에서 탐색이 중단된 경우.

◾ 정답 집합{9,15}와 {15,9}를 다른 답으로 표기했을 경우 25점.

◾ 원소 29를 탐색 공간에 아예 고려하지 않았으나 이에 대한 이유가

채점자가 확인할 수 있도록 기술되지 않은 경우 20점.

◾ 풀이과정에 아래의 문제점이 있는 경우 15점.

1) backtracking tree가 제대로 구성되었으나 정답 집합 {9,15}를 못 찾은 경우.

2) backtracking tree가 제대로 구성되었으나 채점자가 확인할 수 있도록

정답 집합 {9,15}를 제대로 표기하지 않은 경우.

3) 정답 집합 {9,15}를 찾았으나 24를 초과하는 값에 대한 pruning이

제대로 이뤄지지 않은 경우.

4) 정답 집합 {9,15}를 찾았으나 pruning에 관한 설명 및 표시가

채점자가 이해할 수 있도록 충분히 기술되지 않은 경우.

5) 정답 집합 {9,15}를 찾았으며 pruning 기준에 대한 표시가 있으나

탐색 종료에 대한 설명 및 단서가 없는 상태로 트리를 전부 그리지 않은 경우.

6) 정답 집합 {9,15}를 찾았으나 탐색 순서가 오름차순을 만족하지 않는 경우.

◾ 정답 집합 {9,15}를 찾았으나 backtracking tree가

위 기준을 만족하지 않는 상태로 제대로 그려지지 않은 경우 10점.

◾ 아래의 경우 0점.

1) 답이 표기되지 않았고 backtracking tree 또한 제대로 구성되지 않은 경우.

2) 답이 표기되지 않았고 24 미만의 값에서 bound가 발생하는 등

pruning 기준이 일관적임을 채점자가 확인할 수 없는 경우.

[4] 길이가 8인 이진 문자열 “11011010”의 suffix array를 만드는 과정을 단계별로 보이고 최종 결과를 보이시오. 단 사용하는 알고리즘은 정렬하는 substring의 크기를 2배씩 늘려나가는 Manber의 [eqn: THETA (N```log _{2} `N``)] 알고리즘을 사용해야 합니다. (단계별 8점)

i	suffix(i)
0	11011010
1	1011010
2	011010
3	11010
4	1010
5	010
6	10
7	0

Rank	i	suffix(i)
0	2	0
1	5	0
2	7	0
3	0	1
4	1	1
5	3	1
6	4	1
7	6	1

Rank	i	suffix(i)
0	7	0
1	2	01
2	5	01
3	1	10
4	4	10
5	6	10
6	0	11
7	3	11

k=1	k=2

Rank	i	suffix(i)
0	7	0
1	5	010
2	2	0110
3	6	10
4	4	1010
5	1	1011
6	0	1101
7	3	1101

Rank	i	suffix(i)
0	7	0
1	5	010
2	2	0110
3	6	10
4	4	1010
5	1	1011010
6	3	11010
7	0	11011010

Rank	i	suffix(i)
0	7	0
1	5	010
2	2	0110
3	6	10
4	4	1010
5	1	1011010
6	3	11010
7	0	11011010

k=4	k=8                   최종 Suffix Array

(채점 기준)

1) k=1, k=2, k=4, k=8 각 단계에 대해서는 접미사들이 길이 k인 접두사에 의하여

잘 정렬되었다는 것을 보이면 8점씩 부여.

- 접미사들이 해당 조건에 맞게 잘 정렬되어있다는 것만 드러난다면 답안지 상의 표에는

어떤 정보를 기입해도 좋음.

- 잘못 정렬된 접미사가 있는 경우, 실수로 보이는 경우 4점을 부여함.

접미사들이 해당 단계에서 어떤 조건에 의해 정렬된 상태여야 한다는 것을 숙지하지

못한 것으로 보이는 경우 점수 없음.

- 단순히 길이 k의 서로 다른 접두사만을 나열한 경우는 4점만 부여함

(예: k=2에서 0, 01, 10, 11만 적음).

어떤 접두사가 있는지가 중요한 것이 아니라, 각 접미사들의 순위 자체가 중요하기 때문.

2) 최종 표에서는 접미사 배열의 값(7,5,2,6,4,1,3,0)을 올바로 기재해야 8점.

- 결과적으로 접미사 배열 값이 중요한 것이므로, 정렬된 접미사만 나열하고

접미사 배열 값을 기입하지 않은 경우 점수 없음.

- 접미사 배열 값을 잘못 기입한 경우 하나당 2점 감점

[5] 삼각형 내부, 외부, 경계 검사

문제 a, b

- 정답이 맞을 경우 5점, 과정이 있을 경우 5점 추가, 오답인 경우 부분점수 없음

- 해설지의 방법 말고 도형을 나눠서 면적을 합산하는 등 다른 방법으로 풀어도 됨

- 1/2을 안 한 경우, 최종 답에서 부호가 다른 경우 2점 감점, 이외 계산 실수는 오답

a. 점 (6, 4), (-2,-4), (8, 2)로 이루어진 삼각형의 면적을 구하시오. (10)

[eqn: 1 over 2 dmatrix { ````6 & `````-2 & `````8```` # ````4 & `````-4 & `````2```` } = ````1over 2 left( -24 -4 +32 +8 +32 -12 right) ``= 16]

b. 단순 다각형 (1, 1), (9, 5), (6, 10), (5, 7), (-2, 9)의 면적을 구하시오.(10)

[eqn: {1} over {2} {dmatrix{````1&````9&````6&````5&`-2````#````1&````5&````10&````7&`````````9````}} =```` {1} over {2} LEFT ( 5+90+42+45-2-9-30-50+14-9 RIGHT ) ``=``48]

- 도형을 분할해서 문제를 푼 경우, 문제에서 제시한 점의 순서대로 단순 다각형을

만들어서 계산해야 함

c. [eqn: signarea(x,y,z)]를 이용하여 주어진 점 Q가 삼각형 △[eqn: v _{1} v _{2} v _{3}]의 내부, 외부 혹은 경계에 있는지를 알아내고자 한다. 아래 그림의 경우 {P, R}은 외부, {Q}는 내부, {S}는 경계에 있다. 여러분은 세 점 [eqn: x,`y,`z`]로 이루어진 삼각형의 부호 면적을 구해주는 함수 [eqn: signarea(x,y,z)]를 이용해서 삼각형의 부호 면적의 부호에 따라 점 Q가 삼각형 내부에 있으면 +1, 외부에 있으면 –1, 경계에 있으면 0을 return 하는, 즉 {[eqn: +1,`-1,`0]} 중 하나로 return 하는 코드를 작성하시오. 이때, 코드에 필요한 추가 변수는 자유롭게 넣어서 사용할 수 있다. (20점)

// 주어진 점 Q가 삼각형의 내부, 외부, 혹은 경계에 있는지를 확인

int point_in_triangle( v1, v2, v3, Q ) {

int s1, s2, s3 ;

s1 = signarea(v1,v2,Q) ;

s2 = signarea(v2,v3,Q) ;

s3 = signarea(v3,v1,Q) ;

if ( (s1<0) || (s2<0) || (s3<0) ) return –1;

else if ( s1*s2*s3 == 0 )           return 0;

else return 1;

}

- 세 개의 조건 각각 부분점수 : 내부(+1) 6점, 외부(-1) 7점, 경계(0) 7점

조건이 else 문으로 연결된 경우, 선행 조건들이 명확하게 작성해야 관련된 조건 모두 정답으로 인정됨. 그렇지 않을 경우 합쳐서 7점 이하 부분점수

예) s1, s2, s3 중 하나라도 0이 있을 때 경계에 있다고 판단하는 경우

// 오답 예

if ( (s1>0) && (s2>0) && (s3>0) ) return 1;

else if ( s1*s2*s3 == 0 )          return 0;

else return –1;

- 이와 같은 방법으로 작성할 경우, 직선상에 있지만 삼각형 밖인 경우
(그림에서 점 T)도 경계에 있다고 잘못 판단하게 됨

- 이 경우 내부(1)는 정확히 작성했으므로 6점,
경계(0)와 외부(-1)케이스는 합쳐서 7점 이하 부분점수

- 만일 내부도 정확히 작성하지 않은 경우, 전체 점수가 7점 이하

s1+s2+s3과 signarea(v1,v2,v3)는 점의 위치와 관계없이 결과값이 같으므로, 이를 토대로 작성한 조건은 오답처리

s1*s2*s3 < 0일 때 외부라고 판단하는 경우, 그림에서 점 R은 s1<0, s2<0, s3>0 이므로 내부라고 잘못 판단하기 때문에 오답처리

x값의 범위로 경계를 판단한 경우, s1==0이고 [eqn: v _{2 _{x}}] < [eqn: Q _{x}] < [eqn: v _{3 _{x}}] 인 경우라도 그림에서
점 T는 외부에 있으므로 오답처리

부등호나 return 값을 반대로 쓴 경우, 논리 연산자를 잘못 쓴 경우 오답처리

signarea의 return 값을 (0, 1, -1) 라고 가정하고 푼 경우 5점 감점

컴파일 에러는 감점하지 않았음

[6] 그래프 G에서 같은 edge를 공유하고 있지않는 두 정점 [eqn: u,v]를 독립적(independent)이라고 말하며, 서로 독립인 정점의 집합을 독립집합, independent set이라고 한다. 아래 그림 [eqn: G _{1}]에서 {c, f}, {e,g}, {c,b,d,e}, [eqn: G _{2}]에서 {b,f,d}, [eqn: G _{3}]에서 {b,d}는 독립집합의 예이다. 이 문제는 이렇게 응용된다.

예를 들어, 그래프로 표시된 도심에서 프랜차이즈 치킨집 위치를 결정하는데 배정된 치킨 가게들끼리는 같은 도로(edge)에 마주 보고 있지 않도록 하는 것이다. 우리는 이 조건을 만족하며 최대한 많은 수의 치킨집을 열 수 있도록 위치를 특정하는 것은 독립집합 중에서 가장 큰 집합인 최대독립집합(Maximum Independent Set, MIS)을 구하는 문제와 같게 된다.

a) 아래 그래프에서 MIS를 찾으시오. (MIS 중 하나만 찾으면 된다.) (10점)

MIS의 크기는 3. 이 중 하나를 제대로 표시한 경우에는 10점

b) 입력 그래프가 아래와 같은 Tree일 경우 MIS를 구하는 [eqn: O(N``)] time 알고리즘이 있다. 아래 Tree에서 MIS를 찾아 표시하고 Tree에 특화된 [eqn: O(N``)] time 알고리즘을 제시하시오. (10점) 그리고 왜 그것이 MIS를 제대로 찾아주는지 설명하시오. (10점)

MIS를 구하는 알고리즘을 제시할 때, 쉽게 이해 가능한 pseudo-code 형식으로 작성하면 된다. 정점 [eqn: v]에 연결된 모든 vertex 집합을 [eqn: N(v)]로 표시할 수 있다. 그리고 tree는 adjacency list 형식으로 입력된다고 가정한다. 그리고 그래프 G를 탐색하는 DFS(G), BFS(G)가 이미 구현되어 있다고 가정하고, 이를 자유롭게 사용할 수 있으며 필요한 경우 부가 정보 filed를 확장할 수 있다.

Tree는 결국 이분 그래프(bipartite graph)가 됨. 즉 Tree는 모든 vertex는 2개로 U, V로 나누어지고 U끼리 V끼리에는 서로 edge가 없음.

Tree의 vertex를 2개로 나누는 방법은 한 leaf node x에서 시작하여 rooted tree를 만들면서 x에서 거리가 홀수인 vertex 집합을 U, 짝수인 집합을 V로 나누고 x는 V에 포함 시키면 된다. 이 작업은 x에서 BFS(x)를 사용하면 O(N) 시간에 해결될 수 있다.

2번에서 시작하면

V= {2, 3, 6, 8, 4, 10 }, U={1, 4, 5, 7, 9, 11, 13}

이 중에 정답은 U와 V 중에서 더 큰 쪽을 모두 MIS로 하면 된다. 따라서 이 방법을 적용하면 위 Tree에서 7개의 정점을 가지는 MIS를 찾을 수 있다. 따라서 U가 MIS가 된다.

7개를 찾은 경우 10점, 6개... 등은 모두 0점.

c) 이 MIS 문제는 잘 알려진 NP-Complete 문제 중 하나이다. 이 때문에 Greedy 알고리즘을 사용한다. 선택의 기준은 가능한 정점 중에서 차수(degree)가 낮은 정점부터 MIS에 먼저 포함 시키고, 그 정점과 연결된 모든 이웃 정점은 그래프에서 삭제한다. 그리고 남아있는 정점 중에서 다시 차수가(20점)

이러한 차수-기반의 Greedy 알고리즘을 사용했을 때 답을 구하는 경우와 아닌 경우의 그래프를 하나씩 제시하시오. 단 Greedy 전략으로 선택되는 정점의 순서는 표시해야 한다. 그리고 제시한 그래프의 정점의 수는 최소 6 이상 되어야 하며 Tree는 아닌 연결 그래프 형태가 되어야 한다. 따라서 edge는 최소 6개 이상.

Greedy 전략으로 찾을 때 MIS를 제대로 구하는 경우의 그래프 (10점)

그래프만 그린 경우 6점. 그래프를 그리고 greedy하게 선택하는 vetex의 순서를 표시한 경우 10점.

수강생 여러분, 답안은 최대한 채점자에게 친절해야 합니다. 그 답안을 보고 쉽게 정답임을 채점자가 확인할 수 있도록 단계를 꼼꼼하게 기술해야 합니다. 그냥 결과만 냅다 던지고 알아서 보라고 하면 안 됩니다.

Greedy 전략으로 찾을 때 MIS를 제대로 찾지 못하는 경우의 그래프 (10점)

그래프만 제시한 경우 3점 이하. Greedy 전략을 사용할 때의 MIS와 Optimal MIS가 다른 경우를 제시한 경우 10점

수강생 여러분, 답안은 최대한 채점자에게 친절해야 합니다. 그 답안을 보고 쉽게 정답임을 채점자가 확인할 수 있도록 단계를 꼼꼼하게 기술해야 합니다. 그냥 결과만 냅다 던지고 알아서 보라고 하면 안 됩니다.